#include "alg.8-extra-head.h"
#include <stdio.h>
#include <string.h>
// parent(i) = floor((i - 1)/2)
// left(i)   = 2i + 1
// right(i)  = 2i + 2


struct shared_struct* list_find_index(int index, struct shared_struct* head, int size){
    if (index < 0 || index >= size) {
        return 0;
    }

    struct shared_struct* temp = head;
    for (int i = 0; i < index ; ++ i){
        temp = temp + 1;
    }
    return temp;

}

int exchage_nodes(struct shared_struct* node1, struct shared_struct* node2){
    struct shared_struct temp;
    temp.id = node2->id;
    temp.flag = node2->flag;
    strncpy(temp.name, node2->name, TEXT_SIZE);

    node2->id = node1->id;
    node2->flag = node1->flag;
    strncpy(node2->name, node1->name, TEXT_SIZE);

    node1->id = temp.id;
    node1->flag = temp.flag;
    strncpy(node1->name, temp.name, TEXT_SIZE);

    return 0;

}


int shiftUp(struct shared_struct* child, int child_index, int size, struct shared_struct* head){

    //if child is lower than its parent, it gonna shiftUp
   
    
    if (child_index == 0){
        return 0; // 递归链条的结束判断

    }
   
   
    int parent_index = (child_index - 1) / 2;

    if ( parent_index >= size){
        printf("find parent out of range");
        return 1;
    }

    

    struct shared_struct* par_ptr = list_find_index(parent_index, head, size);
    if (par_ptr->id > child->id){
        exchage_nodes(child, par_ptr);
        shiftUp(par_ptr, parent_index, size, head);
        return 0;
    }


}


int shiftDown(struct shared_struct* par, int par_index, int size, struct shared_struct* head){
    int left_kid_index = 2 * par_index + 1;
    int right_kid_index = 2 * par_index + 2;

    if (left_kid_index < 0 || right_kid_index < 0){
        printf("find kid out of range");
        return 1;
    }

    if (left_kid_index >= size){
        return 0; // 递归链条的结束判断
    } else if (right_kid_index >= size){
        struct shared_struct* left_ptr = list_find_index(left_kid_index, head, size);
        
        if (left_ptr->id < par->id || par->flag == 2){
            exchage_nodes(left_ptr, par);
            shiftDown(left_ptr, left_kid_index, size, head);
        }

    } else {
        struct shared_struct* left_ptr = list_find_index(left_kid_index, head, size);
        struct shared_struct* right_ptr = list_find_index(right_kid_index, head, size);


        if (left_ptr->id < par->id || right_ptr->id < par->id || par->flag == 2){
            if (left_ptr->id <= right_ptr->id){
                exchage_nodes(left_ptr, par);
                shiftDown(left_ptr, left_kid_index, size, head);
            } else{
                exchage_nodes(right_ptr, par);
                shiftDown(right_ptr, right_kid_index, size, head);
            }

        }
        return 0;
    }

}

int insert(struct shared_struct* head, int* count, int size, char* name, int id){
    if (*count == size){
        printf("full heap");
        return 1;
    }
    struct shared_struct* rear_ptr = list_find_index(*count, head,size);
    rear_ptr->id = id;
    strncpy(rear_ptr->name, name, strlen(name));
    rear_ptr->flag = 1;

    shiftUp(rear_ptr, *count, size, head);
    (*count) ++;
    return 0;


}

int pop(struct shared_struct* head,  int size, int* count){

    if (*count == 0){
        
        printf("null heap");
        
        return -1;
    }

    (*count) --;
    head->flag = 2;
    return shiftDown(head, 0,size, head);
    
}

void printList(struct shared_struct* head, int size){
    
    struct shared_struct* temp = head;
    
    for (int i = 0; i < size ; ++ i){


        if (temp->flag == 0){
            printf("node %d is not used\n", i);
        } else if (temp->flag == 2) {
            printf("node %d is deleted\n", i);
        } else{
        printf("node %d: name is %s, id is %d\n", i, temp->name, temp->id);
        }
        temp = temp+1;
    }
}

int removeAtIndex(struct shared_struct* head, int size, int index, int* count){

     if (index < 0 || index >= size){
        printf("replace out of range");
        return 1;
    }

    (*count) --;

    struct shared_struct* temp = list_find_index(index, head, size);
    temp ->flag = 2;

    shiftDown(temp,index,size,head);

}

int replace(struct shared_struct * head, int size, int index, char * name, int id){
    if (index < 0 || index >= size){
        printf("replace out of range");
        return 1;
    }

    struct shared_struct* temp = list_find_index(index, head, size);

    int temp_id = temp->id;

    temp->id = id;
    strncpy(temp->name, name, strlen(name));

    if (temp_id > id){
        shiftUp(temp, index,size, head);
    } else {
        shiftDown(temp,index,size,head);
    }
    

}

int searchList(struct shared_struct* head ,int size , int id, int * count){
    

    if (head -> flag != 1){
        return -1;
    }

    struct shared_struct* temp = head;
    
    for (int i = 0; i < * count ; ++ i){
        if (temp -> id == id){
            return i;
        }
        temp = temp+1;
    }

    return -1;
}

int search(struct shared_struct* head ,int size, int id, int par_index, struct shared_struct* par_ptr){
     int left_kid_index = 2 * par_index + 1;
    int right_kid_index = 2 * par_index + 2;

    if (left_kid_index < 0 || right_kid_index < 0){
        printf("search out of range");
        return -1;
    }

    if (par_ptr->flag != 1){
        printf("not found");
        return -1;
    }

    if (par_ptr->id == id ){
        printf("Right way!");
        return par_index;
    }

    if(par_ptr->id > id){
        printf("Too few for the heap");
        return -1;
    }

    if (left_kid_index >= size){
        if (par_ptr->id > id){
            printf("too large for the heap");
            return -1;
        } else {
            printf("not find");
            return -1;
        }
    } else if (right_kid_index >= size){
       
        struct shared_struct* lef_ptr = list_find_index(left_kid_index, head,size);

        return search(head,size,id, left_kid_index, lef_ptr);

    } else {
        

        struct shared_struct* lef_ptr = list_find_index(left_kid_index,head,size);
        struct shared_struct* right_ptr = list_find_index(right_kid_index, head,size);

        int le = search(head,size,id,left_kid_index, lef_ptr);
        int ri = search(head,size,id,right_kid_index,right_ptr);

        if (le != -1){
            return le;
        }
        if(ri != -1){
            return ri;
        }

        return -1;
    }
}